package cn.dglydrpy.study.algorithm.od;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author Yyy
 * @date 2024/11/6 11:45
 * @description  记忆化搜索 TODO
 * 题目描述：“吃货” 和 “馋嘴” 两人分切成奇数块且大小不同的披萨，馋嘴每次拿最大块，
 * 吃货知道馋嘴的想法且第一块可任意拿，求吃货能分得的最大披萨大小总和
 * 
 * 输入
5
8
2
10
5
7
 * 输出：
19
 */
public class Od0010_Pizza {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextInt()){
            int n = scanner.nextInt();
            int[] arr = new int[n];
            for(int i = 0; i<n ;i++){
                arr[i] = scanner.nextInt();
            }
            
            int ans = myAnswer(arr);
            System.out.println(ans);
            System.out.println(answer1(arr));
            
            
        }
    }

    private static int myAnswer(int[] arr) {

        // 是否可拿
        boolean[] help = new boolean[arr.length];
        Arrays.fill(help,true);
        
        int ans = 0;
        
        int ream = arr.length;
        while(ream > 0){
            int ch = ch(arr,help,ream);
            System.out.println("吃货拿" + arr[ch]);
            ans += arr[ch];
            arr[ch] = 0;
            if(ream == arr.length) {
                Arrays.fill(help, false);
            }
            change(ch, arr, help);

            ream--;
            if(ream > 0){
                int cz = cz(arr,help);
                System.out.println("馋嘴拿" + arr[cz]);
                arr[cz] = 0;
                help[cz] = false;
                change(cz, arr, help);
                ream--;
            }
            
        }
        
        return ans;
    }

    /**
     * 状态改变
     * @param ch
     * @param arr
     * @param help
     */
    private static void change(int ch, int[] arr, boolean[] help) {
        if(ch == 0){
            if(arr[1] != 0){
                help[1] = true;
            }
            if(arr[arr.length-1] != 0){
                help[arr.length-1] = true;
            }
        }else if(ch == arr.length-1){
            if(arr[arr.length-2] != 0){
                help[arr.length-2] = true;
            }
            if(arr[0] != 0){
                help[0] = true;
            }
        }else{
            if(arr[ch -1] != 0){
                help[ch -1] = true;
            }
            if(arr[ch +1] != 0){
                help[ch +1] = true;
            }
        }
    }

    /**
     * 要让cz尽可能拿最少
     * @param arr
     * @return 拿走的下标
     */
    private static int ch(int[] arr,boolean[] help,int ream){
        
        int min = Integer.MAX_VALUE;
        int choose = 0;
        for(int i=0;i<arr.length;i++){
            if(help[i]){
                int[] tempArr = Arrays.copyOf(arr,arr.length);
                boolean[] tempHelp = Arrays.copyOf(help,help.length);

                if(ream == arr.length) {
                    Arrays.fill(tempHelp, false);
                }
                
                // 如果拿了这个
                change(i,tempArr,tempHelp);
                tempArr[i] = 0;
                int cz = cz(tempArr, tempHelp);
                
                // 吃货拿不了了
                if(cz == -1){
                    return i;
                }
                
                if(tempArr[cz] <= min){
                    min = tempArr[cz];
                    choose = i;
                }

            }
        }
        return choose;
    }

    /**
     * 每次都会拿剩下可以拿的max
     * @param arr
     * @return 拿走的下标
     */
    private static int cz(int[] arr,boolean[] help){

        int maxIndex = -1;
        int max = Integer.MIN_VALUE;
        for(int i=0;i<arr.length;i++){
            if(help[i]){
                if(arr[i] > max){
                    maxIndex = i;
                    max = arr[i];
                }
            }
        }

        return maxIndex;
    }
  

    // 存储每块披萨的大小
    static int[] arr;
    // 存储中间结果的二维数组
    static int[][] f;

    public static int answer1(int[] slices) {
        int n = slices.length;
        int da = 0;
        f = new int[n][n];
        arr = slices;

        // 先将 f 数组用 -1 填充，表示该状态还未被计算过
        for (int i = 0; i < n; i++) {
            Arrays.fill(f[i], -1);
        }
        for (int i = 0; i < n; i++) {
            // 尝试从每一块披萨开始作为吃货的第一块选择，计算后续能获得的最大总和，然后取最大值更新 da
            da = Math.max(da, arr[i] + dfs(i + 1, i + n - 1, n));
        }
        return da;
    }

    /**
     * 
     * @param R  表示当前状态下正在考虑的其中一块披萨的索引
     * @param L  表示当前状态下另一块披萨的索引
     * @param n  表示披萨的总块数
     * @return
     */
    public static int dfs(int R, int L, int n) {
        // 确保索引在合法范围内，如果超出了数组的范围，通过取模操作将其调整回合法范围内
        R = (R + n) % n;
        L = (L + n) % n;
        if (arr[R] > arr[L]) {
            // 如果当前 arr[x]对应的披萨比 arr[y]大，那么更新 x 的索引
            R = (R + 1) % n;
        } else {
            // 如果当前 arr[y]对应的披萨比 arr[x]大，那么更新 y 的索引
            L = (L - 1 + n) % n;
        }
        // 如果当前状态（x 和 y 对应的位置）已经计算过，直接返回存储在 f[x][y]中的结果
        if (f[R][L]!= -1) {
            return f[R][L];
        }
        // 当 x 和 y 指向同一位置时，说明已经到达了边界情况，返回该位置的披萨大小
        if (R == L) {
            return arr[R];
        }
        // 递归地计算吃货选择当前披萨（要么是 arr[x]要么是 arr[y]）后能获得的最大总和，
        // 取两者中的较大值存储在 f[x][y]中，并返回该值
        f[R][L] = Math.max(arr[R] + dfs(R + 1, L, n), arr[L] + dfs(R, L - 1, n));
        return f[R][L];
    }
}
